算法概论实验九 贪心法

发表于 | 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
实验九

实验目的与要求：
（1）	掌握贪心法的基本思想和设计方法。

1．区间划分问题
【问题描述】
给定一组报告，其中的每个报告设置了一个开始时间si和结束时间fi。设计与实现一个算法，对这组报告分配最少数量的教室，使得这些报告能无冲突的举行。


2．最小延迟调度问题
【问题描述】
    假定有一单个的资源在一个时刻只能处理一个任务。现给定一组任务，其中的每个任务i包含一个持续时间ti和截止时间di。设计与实现一个算法，对这组任务给出一个最优调度方案，使其对所有任务的最大延迟最小化。

#1．区间划分问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<iostream>
using namespace std;

#define N 100

struct Report
{
	int num;//报告编号
	int begin;//开始时间
	int end;//结束时间
	bool flag;//是否已分配教室
	int classroom;//教室号
};

void QuickSort(Report* rep,int f,int t)//一开始将所有报告按结束时间排序
{
	if(f<t)
	{
		int i=f-1,j=f;
		Report r=rep[t];
		while(j<t)
		{
			if(rep[j].end<=r.end)
			{
				i++;
				Report tmp=rep[i];
				rep[i]=rep[j];
				rep[j]=tmp;
			}
			j++;
		}
		Report tmp1=rep[t];
		rep[t]=rep[i+1];
		rep[i+1]=tmp1;
		QuickSort(rep,f,i);
		QuickSort(rep,i+2,t);
	}
}

int select_room(Report *rep,int *time,int n)
{
	//第一个报告分给第一个教室
	int i=1,j=1;//i报告，j教室
	int sumRoom=1;
	int sumRep=1;//教室已分配的报告数
	time[1]=rep[0].end;
	rep[0].classroom=1;

	for(i=1;i<n;i++)
	{
		for(j=1;j<=sumRoom;j++)
		{
			if((rep[i].begin>=time[j])&&(!rep[i].flag))
			{
				rep[i].classroom=j;
				rep[i].flag=true;
				time[j]=rep[i].end;
				sumRep++;
			}
		}
		if(sumRep<n&&i==n-1)//报告没有分配完
		{
			i=0;
			sumRoom++;
		}
	}
	return sumRoom;
}

int main()
{
	int n;
	Report rep[N];
	int time[N];//每个教室最后一个报告的结束时间
	cout<<"请输入报告数量:"<<endl;
	cin>>n;
	int i;
	for(i=0;i<n;i++)
	{
		//初始化
		time[i+1]=0;//time[1]~time[10]
		rep[i].num=i+1;//编号1~10
		rep[i].flag=false;
		rep[i].classroom=0;

		cout<<"报告"<<i+1<<"开始时间:";
		cin>>rep[i].begin;
		cout<<"报告"<<i+1<<"结束时间:";
		cin>>rep[i].end;
	}
	QuickSort(rep,0,n-1);
	int roomNum=select_room(rep,time,n);
	cout<<"所用教室总数为:"<<roomNum<<endl;
	for(i=0;i<n;i++)
	{
		cout<<"活动"<<rep[i].num<<"在教室"<<rep[i].classroom<<"中"<<endl;
	}
	system("pause");
	return 0;
}

#2．最小延迟调度问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
using namespace std;

#define N 100

struct Mission
{
	int num;
	int last;
	int end;
};

void QuickSort(Mission *mi,int f,int t)
{
	if(f<t)
	{
		int i=f-1,j=f;
		Mission m=mi[t];
		while(j<t)
		{
			if(mi[j].end<=m.end)
			{
				i++;
				Mission tmp=mi[i];
				mi[i]=mi[j];
				mi[j]=tmp;
			}
			j++;
		}
		Mission tmp1=mi[t];
		mi[t]=mi[i+1];
		mi[i+1]=tmp1;
		QuickSort(mi,f,i);
		QuickSort(mi,i+2,t);
	}
}

int main()
{
	int n;
	cout<<"请输入任务总数:"<<endl;
	cin>>n;
	Mission mi[N];//Mission[0]~Mission[n-1]
	int start[N+1];//排好序的任务的开始时间，start[1]~start[n]
	int i;
	for(i=0;i<n;i++)
	{
		mi[i].num=i+1;
		cout<<"任务"<<i+1<<"的持续时间为:";
		cin>>mi[i].last;
		cout<<"任务"<<i+1<<"的截止时间为:";
		cin>>mi[i].end;
	}
	QuickSort(mi,0,n-1);
	int delay=0;
	start[1]=0;
	if(start[1]+mi[0].last>mi[0].end)
	{
		delay+=start[1]+mi[0].last-mi[0].end;//如果开始时间+持续时间>截止时间，累计延迟
	}
	for(i=1;i<n;i++)
	{
		start[i+1]=start[i]+mi[i-1].last;
		if(start[i+1]+mi[i].last>mi[i].end)
		{
			delay+=start[i+1]+mi[i].last-mi[i].end;
		}
	}
	cout<<"延迟最小为:"<<delay<<endl;
	for(i=0;i<n;i++)
	{
		cout<<"任务"<<mi[i].num<<"的执行时间:["<<start[i+1]<<","<<mi[i].last+start[i+1]<<"]"<<endl;
	}
	system("pause");
}